#include <bits/stdc++.h>
using namespace std;
const int maxn = 10001;
struct Edge
{
	int v;
	int nxt;
} e[maxn<<1]; //记录边
int head[maxn],cnt=0,n;  //每个顶点作为链表的头
int siz[maxn],son[maxn],fa[maxn],level[maxn],h,w; 

void addedge(int u,int v)
{
	e[++cnt] = (Edge) {v,head[u]};
	head[u] = cnt;
}

void dfs(int u)
{
	cout << u << endl;
	for (int v = head[u]; v; v=e[v].nxt)
		dfs(e[v].v);
}

string convert(int u) 
{
	string s="";
	while(u)
	{
		s=char(u%10+'0') + s;
		u/=10;
	}
	return s;
}

void dfs(int u,int dep)
{
	siz[u] = 1;  
	for (int v = head[u]; v; v=e[v].nxt)
	{
		int uson;
		fa[uson = e[v].v] = u;
		dfs(uson, dep+1);
		siz[u] += siz[uson];
		son[u]++;
	}
	w = max(w, son[u]);
	h = max(h, level[u] = dep);
}

int main() 
{
	cin >> n;
	for (int i=1;i<n;i++)
	{
		int u,v;
		cin >> u >> v;
		addedge(u,v);
	}
	dfs(1,1);
	cout << h << " " << w << endl;
	for (int i=1;i<=n;i++) cout << son[i] <<" ";
	cout << endl;
	for (int i=1;i<=n;i++) cout << fa[i] <<" ";
	cout << endl;
	for (int i=1;i<=n;i++) cout << siz[i] <<" ";
	cout << endl;
	return 0;
}